This invention relates to an apparatus and method for scanning a three dimensional object.
Real-world, three-dimensional objects whether with natural form (e.g. geographical, plant, human or animal-like) or man-imagined form (e.g. sculptures, reliefs, cars, boats, planes or consumer products) are difficult to scan. This is because of features such as rapidly varying surface normals and surfaces for which a line of sight is difficult because it is partially obscured by other parts of the object.
Scanning machinesxe2x80x94also known as digitizing machinesxe2x80x94for scanning objects or parts of objects can be categorised into two types: computer numerically controlled (CNC) and manually operated. A scanning machine includes a unit that contains a sensing means commonly referred to as a probe.
Objects or parts of objects can be scanned on CNC scanning machines with a number of computer numerically controlled (CNC) linear and rotating motor-driven axes. Different CNC machines can move/reorient the probe or the objectxe2x80x94or bothxe2x80x94by a combination of translation and rotation about these axes. Different machine designs are suited to different classes of objects. Probes can be temporarily or permanently attached to most types of CNC machine tool or CNC coordinate measuring machine which can then be used for scanning. As examples, small and simple 3-axis CNC milling machines may be used or large, complex 5-axis machines may be used. The points captured by CNC machines are usually on a regular grid and the rate varies from around 1 point per second up to around 20,000 points per second depending on the technology being used and the object being scanned. The points from these scanning machines are accurate to the order of 0.05 mm. CNC machines with probes scan by executing one or more programs that move the axes of the machine such that there is relative motion between the probe and the object.
CNC machines are expensive, partly because of the incorporation of motors and the associated equipment for assuring rejection motion such as linear guides and drive screws. Few CNC machines are flexible enough so that the probe can be oriented in six degrees of freedom so as to scan the complete surface of a complex object. Even when a CNC machine has six degrees of freedom, it is often not sufficiently flexible so as to position the probe to scan the complete surface of the object without colliding with the object. When the object is a person or expensive, the risk of using a CNC machine may be unacceptable and there would be a necessity to make a machine to meet both the safety and scanning requirements of the application. The programming of a CNC machine so that the surface of the object is completely scanned without a collision of the probe or machine with the object is often highly complex. Usually the design of the machine and the degrees of freedom inherent in the design and limitations in the probe design such as the standoff distance during scanning between the probe and the object, mean that it is impossible to come up with a scanning strategy that will scan the complete surface of the object. It is common that the object has to be manually picked up and replaced in a different position and or orientation one or more times during scanning. Each time that this occurs, the object has to be registered to a uniform coordinate system such that the data from the different scans can be accurately combined.
Manually operated scanning machines can be categorised into three types: horizontal arm machines, multiply jointed arms and devices based on remote position sensing means.
Manually driven, horizontal arm measuring machines usually have three orthogonal axes and are usually based on a travelling column design. These machines are usually quite large with the bed being at floor level so large items such as cars can easily be moved onto and off them. Often motors can be engaged on one or more axes to aid the manual movement of the machine. The probe is normally mounted at a fixed orientation on the end of the horizontal arm. This orientation may be changed and various devices may be attached between the end of the horizontal arm and the probe to aid the changing of the orientation, most of these devices having two axes. Horizontal arm machines have the disadvantage of not being able to easily orient the probe in six degrees of freedom. The limited flexibility in the design of a horizontal arm machine makes most of the far side of the object unscannable.
Multiply jointed arms commonly comprise multiple linkages and are available for scanning complex objects. A multiply jointed arm typically has 6 joint axes but may have more or less joint axes. At the end of the multiply jointed arm there is usually a tip reference pointxe2x80x94such as a sphere whose centre is the reference point or a cone ending in a point. Scanning is carried out by bringing the point or sphere into contact with the object being scanned. The computer monitoring the multiply joined arm then measures the angles at all the joints of the multiply jointed arm and calculates the position of that reference point in space. The direction of the last link in the multiply jointed arm is also calculated. Positions can typically be output continuously at a rate of around 100 points per second, but the rate can be much more or much less. The accuracy is of the order of 0.1 to 0.5 mm. The points from the arm are usually sparse and unorganised. The sparseness and lack of organisation of the points makes it difficult to provide enough information for constructing a computer model of the object that is of acceptable quality. A multiply jointed arm with multiple linkages has a limited working volume. In general, if a larger working volume is required, the arms become very expensive, less accurate and tiring, difficult to operate. The limited working volume can be increased by leapfrogging in which the whole arm/base is moved to access another volume, but this requires a time consuming system of registering at least 3 points each time the arm is moved and recombining the data sets from each arm position. Manufacturer""s of multiplying jointed arms provided pre-calibrated arms and test methods that the user may employ to make sure that the arm is still calibrated to an acceptable accuracy. Such test methods use for example the standard tip reference point at the end of the arm and a reference sphere or a ball-bar which is a rod with two cylindrical cups that has a precise known distance between a home ball and a end of arm ball. As the arm tip at the end of the ball bar is moved on the surface of spherical domain the arm records positions which are later compared to a perfect sphere and error estimates for the arm are output.
Remote position sensing devices include hand-held devices that transmit or receive position information in a calibrated reference volume using different physical methods including electromagnetic pulses and sound waves. A hand-held device may be connected to the rest of the system by means of a cable. These devices are prone to generating scanned points with very large errors and some devices cannot work when the object being scanned has metallic components. They are less accurate than multiply jointed arms with accuracies of the order of 0.5 xcexcm upwards.
There are three broad categories of scanning probe that could be mounted on the end of a multiply jointed scanning machine: point, stripe and area probes. Point probes measure a single point at a time and technologies include mechanical contact methods and optical distance measurement methods. Stripe probes measure a number of points in a line either simultaneously or rapidly in a scanned sequence; the most common stripe technology is laser stripe triangulation. Area probes measure a two-dimensional array of points on a surface either simultaneously or in a scanned sequence; the most common technologies are interference fringe and multiple stripe projection. Some area methods require the device to be held still for a few seconds during data capture. Stripe and area methods have an in-built speed advantage over point methods as there are less motion of the probe relative to the object. There are differences between the methods in terms of accuracy and cost but these do not generalise with category, for example a particular area technology may be cheaper and more accurate than another point technology.
Means of capturing independent reference/feature points by contact are well known and efficient. Structured light using stripe or area methods is not good at capturing independent feature points because there is no way for the operator to align a known point on the object with a point on the stripe or in the area.
Geometrical errors in the scanning process stem from many sources. CCD cameras can typically capture video at 25 frames per second. One major disadvantage in normal use is that from any given demand for a frame there is a variability of 40 msecs until the start of capture of that frame. If the probe is being moved at for example 100 mm/sec, this can lead to a geometrical error of 4 mm in the probe""s data. The duration of frame capture depends upon the shutter speed e.g. {fraction (1/100 )} sec is 10 msecs. One major disadvantage in normal use is that if the probe is being moved with a slow shutter speed, an additional geometrical error is created. An arm is typically connected to a computer by a serial cable with arms typically generating positions at 125 positions per second as they move; at this rate there is a variability of 8 msecs between when a position is needed at the computer and when it arrives. This can also introduce a geometrical error when the probe is moving. The total variabilities of the CCD camera and the arm can cause large aggregate errors.
There is a wide range of formats for 3D information in current use. These include the general categories: point formats, polygon formats and complex surface formats.
Point formats include: independent points, lines of points where a plane intersects with a surface, 2.5D areas of points which are commonly known as range images which are single valued in Z and 3D point arrays which are often generated by medical scanners. The point formats have many standard representations including the Range Image Standard (RIS) resulting from the European ESPRIT Research and Development Project 6911, IGES and DXF published by AutoDesk Inc in the USA.
Polygon formats include polygons of different geometrical form. Polygons may be 3 or more sided and formats may include mixed numbers of sides or always the same number of sides. Special cases such as Delaunay triangulation can specify the positioning of vertices and the relative lengths of sides of polygons. Standard representations of polygon formats include STL published by 3D Systems Inc in the USA, IGES, OBJ published by Wavefront Inc in the USA and DXF.
Complex surface formats include Bezier, NURBS, and COONS patches. Standard representations of complex standards formats include IGES, VDA-FS, SET, STEP and DXF.
The objective of scanning can be simply to gather a number of three-dimensional points on the surface of the object, or it may be to create a computer model in a format that is fuseful for the application in which the model is to be used. It is generally true that a cloud of points alone is not much use in many applications and that more structure is needed to make a computer model efficient to manipulate in typical applications such as visualisation, animation, morphing and surface or solid modeling.
There are often benefits to be gained from reducing the size of the files associated with the model formats. Any file, whatever its format can be compressed using standard reversible utilities such as PKZIP/PKUNZIP from PKWare in the USA. With 3D point arrays, an octet format can be used to reduce the size of the arrays that represent a surface; an octet format splits a cubic volume into eight, smaller cubes and only further subdivides cubes by eight if they contain information; an octet format is reversible. Moving from unstructured point representation to polygon or complex surface formats often produces large compressions but relies on approximations so the process is nearly always irreversible and it is also difficult to automate so as to give good enough results. Chordal tolerancing is a commonly used method of reducing the quantity of discrete points in a 2D or 3D polyline. As an intermediate data structure it has disadvantages in that: the intermediate data structure does not record the orientation of each stripe, it does not record breaks in the data but assumes that all the points are connected by a surface and it does not record jumps in the data such as those caused by occlusions.
Most scans today are carried out using a multiply jointed arm with a tip reference point. It is usual to firsf mark the object to be scanned with a permanent or temporary marking device such as an ink pen or scribe to create a polygonal network of splines. A single point is then scanned at each network intersection. On the computer, the points are linked together into a polygonal structure. The overall process (marking, scanning and linking) of creating a 3D polygonal model is at a typical rate of 1 point (or vertex on the model) every 3 seconds. In some implementations, the network is not marked on, but appears on a computer display as each point is scanned; with this implementation, the network is built up interactively. This method is suitable for models with a relatively small number of vertices i.e. hundreds and thousands. The method is very slow, requires skill, patience and concentration, is expensive in human time particularly for large, detailed objects that can take 3 weeks to scan.
An alternative method of scanning with a multiply jointed arm and contact tip reference point has often been tried in which independent points are rapidly captured without the aid of network. The points are then input into a surfacing software package which then constructs a polygonal network between the points. However, the xe2x80x98polygonisationxe2x80x99 of unorganised data points is usually very slow and speed decreases significantly as the number of points increases. The results are usually so poor as to be unacceptable. There is usually a significant amount of hand editing of the data required.
Where a CNC scanning machine is used, the intermediate data structures are usually range images. A number of unregistered range images may be registered, polygonised and integrated together. The raw data is a number of range images of an object: typically from 5 to 20 in number, with each one either being a cylindrical or a linear range image. The process is not automatic and requires a combination of operator guidance and automated execution of algorithms. The operator first tries to align (i.e. register) the range images to each other on the computer using a graphics display. This process is not accurate and is followed by an automatic least squares fitting process that attempts to adjust the position and orientation of each range image such that they fit together as well as possible; this process is lengthy often taking hours on a powerful computer. Each range image is then independently polygonised into a network of 2.5D triangular polygons. Finally, the networks of triangular polygons are integrated together. The output is a single, 3D polygon dataset. The process is expensive both in terms of capital equipment cost and people time. It can take up to two years to become skilled enough to scan objects to produce good enough models. It can work and produce good results for detailed objects.
For smooth objects, where the objective is to create complex surface formats, a coordinate measuring machine with a contact tip reference point is commonly used. It is usual to mark up the object with the desired surface patch boundaries by using a marking device such as a pen or a scribe. These patch boundaries are then hand digitised with the contact point probe. The software package then generates a CNC scanning program that automatically takes more points along the boundaries and inside the patches. The software then automatically generates a first attempt at the surface model. This method is used because it is quicker and easier for the operator to define patch boundaries that will lead to a surface model with the desired structure before scanning than to define the patch boundaries after scanning using a software package on a computer with a display showing the scanned points. It can take several days and often weeks to create patch boundaries which are usually splines and then create the patches and then trim the patches to form a surface model by using only the scanned points and a computer.
Scanned data points have been displayed in real-time. The display of points has the disadvantages of easily becoming confusing to interpret and also that the observer does not know when parts of the object""s surface have been missed during scanning.
According to the present invention, there is provided a scanning apparatus for scanning an object to provide a computer model thereof, comprising means for scanning the object to capture data from a plurality of points on the surface of the object where the scanning means captures data from two or more points simultaneously; means for generating intermediate data structures therefrom; means for combining the intermediate data structures to provide the model; means for display and means for manually operating the scanning apparatus.
The apparatus is most efficient in the quest to reduce the time and cost of generating a computer model from a real world object by means of scanning with both time and cost reductions of an order of magnitude achieved over conventional techniques. The model is generated automatically from the intermediate data in a form that may be immediately usable in a wide range of applications.
The scanning means may use structured light to more quickly scan the surface of the object. The scanning means may also be operable to sense the colour of the surface of the object, resulting in a model more like the real world object.
Preferably the scanning means therein comprises means for generating a signal for scanning the object, signal detection means for detecting the signal reflected from the object and means operable in response to the detected signal to provide the data for the intermediate data structure.
The structured light is preferably projected as a plane of light such that a stripe is formed on a viewing plane that is situated normal to the projection axis of the signal generating means and situated at the average stand-off distance from the signal generating means.
Alternatively the structured light may be projected such that a pattern is formed on an area of a viewing plane that is situated normal to the projection axis of the signal generating means and situated at the average stand-off distance from the signal generating means.
The signal generating means may be an illumination source such as a laser diode or one or more bulbs.
During scanning, the operator may see the surface he has scanned appearing in real-time as rendered polygons on the display such that he may more easily scan the object. The operator may mount the object on a turntable and then he may scan from a seated position rather than walking around the object. The scanning means can be mounted on many different types of manual machines, giving enhanced flexibility for objects ranging in size from small to very large. The scanning means can be mounted on a multiply jointed arm for accurate scanning. The scanning means may be a self-contained unit that contains a remote position sensor and incorporates a display to give the most flexibility in scanning.
According to the invention there is also provided a method for scanning an object to provide a computer model thereof, comprising the following steps:
manually scanning the object with a signal by manual operation of a signal generating means:
detecting the reflected signal
generating intermediate data structures for the points;
combining the intermediate data structures to provide the model; and
displaying the data, wherein the data is captured from a plurality of points on the surface of the object simultaneously.
According to a further aspect of this method of the invention the colour data is also captured from the object and then mapped on to the model.
Preferably the data is displayed simultaneously as a plurality of display polygons.